
lst = [90, 39, 77, 89, 62, 58, 10]
# 从小到大排序
# lst.sort()
# lst = sorted(lst)
# print(lst)

#冒泡排序
# for i in range(len(lst)-1):
#     for j in range(len(lst)-1-i):
#         if lst[j] > lst[j+1]:
#             lst[j], lst[j+1] = lst[j+1], lst[j]
#
# print(lst)

# 选择排序
# for i in range(len(lst)-1):
#     for j in range(i+1,len(lst)):
#         if lst[i]>lst[j]:
#             lst[i],lst[j]=lst[j],lst[i]
# print(lst)

lst = [30, 90, 80, 79, 66, 99, 23]
#插入排序
for i in range(1,len(lst)):
    index =i
    for j in range(i-1,-1,-1):
        if lst[i]<lst[j]:
            index=j
        else:
            break
    lst.insert(index,lst[i])
    lst.pop(i+1)
print(lst)

# 快速排序
def sort(lst):
    if len(lst)<=1:
        return lst
    else:
        less = []
        more = []
        middle = []
        for i in lst:
            if i< lst[0]:
                less.append(i)
            elif i >lst[0]:
                more.append(i)
            else:
                middle.append(i)
        less = sort(less)
        more = sort(more)
        return less+middle+more
lst = sort(lst)
print(lst)



# 归并排序
def a(lst):
    middle = len(lst)//2
    if len(lst) <= 1:
        return lst
    left=a(lst[:middle])
    right=a(lst[middle:])
    return b(left,right)

def b(left,right):
    l=0
    r=0
    result=[]
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result+=left[l:]
    result += right[r:]
    return(result)
print(a(lst))


